We present an efficient algorithm for calculating $q$-gram frequencies onstrings represented in compressed form, namely, as a straight line program(SLP). Given an SLP $\mathcal{T}$ of size $n$ that represents string $T$, thealgorithm computes the occurrence frequencies of all $q$-grams in $T$, byreducing the problem to the weighted $q$-gram frequencies problem on atrie-like structure of size $m = |T|-\mathit{dup}(q,\mathcal{T})$, where$\mathit{dup}(q,\mathcal{T})$ is a quantity that represents the amount ofredundancy that the SLP captures with respect to $q$-grams. The reduced problemcan be solved in linear time. Since $m = O(qn)$, the running time of ouralgorithm is $O(\min\{|T|-\mathit{dup}(q,\mathcal{T}),qn\})$, improving ourprevious $O(qn)$ algorithm when $q = \Omega(|T|/n)$.
展开▼
机译：我们提出了一种有效的算法，用于计算以压缩形式（即，作为直线程序（SLP））表示的字符串上的$ q $ -gram频率。给定大小为$ n $的SLP $ \ mathcal {T} $表示字符串$ T $，算法将问题简化为加权的$ q $ -gram，从而计算出$ T $中所有$ q $ -grams的出现频率。大小为$ m = | T |-\ mathit {dup}（q，\ mathcal {T}）$的类似于atrie的结构的频率问题，其中$ \ mathit {dup}（q，\ mathcal {T}）$是表示SLP就$ q $ -gram捕获的冗余量的数量。减少的问题可以在线性时间内解决。由于$ m = O（qn）$，因此我们的算法的运行时间为$ O（\ min \ {| T |-\ mathit {dup}（q，\ mathcal {T}），qn \}）$，当$ q = \ Omega（| T | / n）$时，使用$ O（qn）$算法。
展开▼
